//
// Created by denglibin on 2020/7/1.
// 希尔排序： 按照跨度分组，对每一个分组使用插入排序（插入排序在大部分元素有序时，效率高），减少跨度 直到跨度为1
// 比如 跨度是  4，则 0，4，8，12...为一组；1，5，9，13...为一组

#include "../header/sort.h"

static void shell_sort(int arr[], int len)
{
    int gap = len / 2;
    while (gap > 0)
    {
        // 对每一组进行插入排序（不是排完一组再排另一组，而是直接根据当前元素在哪一组就在该组进行排序）
        for (int i = gap; i < len; i++)
        {
            int j = i - gap; // 该组的前一个元素
            while (j >= 0)
            {
                if (arr[j] > arr[j + gap])
                { // 该组的当前相邻两个元素比较
                    swap_num(arr + j, arr + j + gap);
                }
                j -= gap; // 往前移（改组的前一个元素）
            }
        }
        gap /= 2; // 减少跨度
    }
}

static int main6()
{
    int arr[11] = {3, 4, 5, 1, 2, 9, 10, 78, 100, 89, 65};
    shell_sort(arr, 11);
    print_arr(arr, 11);
    return 0;
}